import java.util.*;


class Student implements Comparable<Student>{
    public  int age;
    public String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }
}

//比较器
class NameComparator implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        return o1.name.compareTo(o2.name);
    }

}class AgeComparator implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }
}


// 实现一个比较器
class Incmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
       // return o1.compareTo(o2); // 这是小根堆
        return o2.compareTo(o1);  // 这是大根堆
    }
}

public class Main {

    public static void main(String[] args) {

        // 小根堆变成大根堆

        // PriorityQueue 默认的是小根堆
        Queue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student(10,"zhangsan"));
        priorityQueue2.offer(new Student(10,"lisi"));

        System.out.println("asfafa");

        Incmp incmp = new Incmp();

        Queue<Integer> priorityQueue1 = new PriorityQueue<>(incmp); // 传入比较器

        // 也可以用到匿名内部类的写法
    /*    Queue<Integer> priorityQueue3 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
*/

        // 第三种写法 lambda 表达式的写法
       // Queue<Integer> priorityQueue3 = new PriorityQueue<>(((o1, o2) -> {return o2.compareTo(o1);}));

        priorityQueue1.offer(1);
        priorityQueue1.offer(2);
        System.out.println("asfas");

    }

    public static void main1(String[] args) {
        System.out.println("Hello world!");

        // 优先级队列
        // 队列是一种先进先出的队列，操作的数据可能带有优先级,一般出队列时，可能需要优先级高的元素先出队列
        // 在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数
        //据结构就是优先级队列(Priority Queue)。



        //****2. 优先级队列的模拟实现****
        //JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整

        //****2.1 堆的概念****
        //如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一
        //个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大
        //堆)。将根节点最大的堆叫做 最大堆或大根堆，根节点最小的堆叫做 最小堆或小根堆

        // ****堆的性质：****
        //堆中某个节点的值总是不大于或不小于其父节点的值；
        //堆总是一棵完全二叉树。

        // 小根堆就是 ： 所有根节点的值总是小于其孩子节点的值
        // 大根堆就是 ： 跟小根堆时相反的

        // 2.2 堆的存储方式
        //从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，
        //对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节
        //点，就会导致空间利用率比较低。，采用链式存储的方式比较好



        //将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
        //如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
        //如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
        //如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

        //****2.3 堆的创建****
        //2.3.1 堆向下调整
        //对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
        //               27
        //          15        19
        //      18      28 34     65
        //    49   25  37



        // 将其变成大根堆
        // 需要先把这棵树的最后一个子树调成大根堆

        // 找左右子树的最大值将其交换
        TestHeap testHeap = new TestHeap();
        int[] array = { 27,15,19,18,28,34,65,49,25,37 };
        testHeap.initElem(array);
        testHeap.creatHeap(); // 这就是大根堆
        System.out.println("!!!!!!!!!!!!!!!");


        // 堆的插入和删除
        // 把新的数据插入到有效数组的随后一位
        // 如果不是本题中的大根堆的话 就 进行向上调整
        // 让 子节点和根节点比较 ， 大了就换，从下面往上调整
        // testHeap.offer(80);
      //  System.out.println("-----");

        // //堆的删除
        //
        //    //注意：堆的删除一定删除的是堆顶元素。具体如下：
        //    //1. 将堆顶元素对堆中最后一个元素交换
        //    //2. 将堆中有效数据个数减少一个
        //    //3. 对堆顶元素进行向下调整
        testHeap.pop();
        System.out.println("23156456456");

        // 堆的 peek
        System.out.println(testHeap.peek());

    }

    public static void main2(String[] args) {
        // ****3.常用接口介绍****
        //3.1 PriorityQueue的特性

        //Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线
        //程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();


        //关于PriorityQueue的使用要注意：
        //1. 使用时必须导入PriorityQueue所在的包，即：
        //import java.util.PriorityQueue;
        // 2. PriorityQueue中放置的元素 必须要能够比较大小 ， 不能插入无法比较大小的对象 ，否则会抛出
        //ClassCastException异常
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        priorityQueue1.offer(10);
        priorityQueue1.offer(2);
        System.out.println(priorityQueue1.poll());
        // 从这个输出结果可以看出 PriorityQueue<> 底层默认的是一个小根堆
        //首先添加的元素是能够比较大小的
        Queue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student(10));
        priorityQueue2.offer(new Student(20));
        System.out.println(priorityQueue2.poll());
        // 这个会发生 ClassCastException 报错

        //3. 不能插入null对象，否则会抛出NullPointerException
        priorityQueue2.offer(null);
        // 4. 没有容量限制(指的是最多整数的最大值)，可以插入任意多个元素，其内部可以自动扩容

        //5. 插入和删除元素的时间复杂度为O(logN)

        //6. PriorityQueue底层使用了堆数据结构

        //7. PriorityQueue默认情况下是小根堆---即每次获取到的元素都是最小的元素

    }

    public static void main3(String[] args) {
        //****3.2 PriorityQueue常用接口介绍****
        //***1. 优先级队列的构造***
        List<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new PriorityQueue<>(list); // 可以这样传值
        
    // oj 题
        int[] array = {1,5,43,3,2,7,98,41,567,78};
        int[] ret =  maxK(array,3);
        System.out.println(Arrays.toString(ret));
    }
    // 面试题 17.14. 最小K个数
    // 时间复杂度
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0){
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(arr.length);
        // 建立小根堆
        for ( int x: arr ) {
            minHeap.offer(x); //遍历x
            // 这一部分的时间复杂度是 O(N*logN)
        }
        // 这个时间复杂度是k*logN
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    //方法二 ： 你如果想找前k个最小的元素
    // 那么你就需要把数组的前k个元素建立成大根堆
    // 如果你想找前k个最大的元素
    // 那么你就需要把数组的前k个元素建立成小根堆

    // 以找最大元素建立小根堆为例
    // 之后从 k + 1 个元素开始遍历
    // 如果第k+1个元素的值 与 此时的小根堆的堆顶元素进行比较
    // 如果小于堆顶元素 是不需要入堆的 ， 这个元素一定不是前k个元素的最大值
    // 如果大于堆顶元素 说明这个堆顶元素不是最大值 ， 所以这时候要把堆顶元素出出去 ，然后把这个值放进来 在调整为小根堆
    // 依次向后比较

    //（小根堆中的前k个最大的值 堆顶元素 是这k个最大值里面 最小的 。 当遍历到数组元素大于堆顶的时候， 说明 此时堆顶的元素 一定不是前
    // k个最大的值）

    // 同理 找最小元素建立大根堆相反

    // 实现一个第k大的元素 // (前k个最大的元素中 的 堆顶的元素就是第k大的元素)

    // 这个地方的时间复杂的是 N*logK
    public static int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k == 0){
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k); // 建立小根堆
        // 遍历数据的前k个，放到堆当中
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        // 遍历剩下的k-1个 ， 并 每次和堆顶元素进行比较
        for (int i = k; i < arr.length ; i++) {
            if(minHeap.peek() < arr[i]){
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
           ret[i] =  minHeap.poll();
        }
        return ret;
    }

        public static void main4(String[] args) {
        // 对象大小的比较
        // equals 的比较结果只是 true false // 只能判断两个对象是否相同


        Student student1 = new Student(10,"zhangsan");
        Student student2 = new Student(20,"zhangsan");
        System.out.println(student1.equals(student2));
        System.out.println(student1.compareTo(student2));

        NameComparator nameComparator = new NameComparator();
        int ret = nameComparator.compare(student1,student2);
        System.out.println(ret);

        AgeComparator ageComparator = new AgeComparator();
        int ret2 = nameComparator.compare(student1,student2);
        System.out.println(ret2);
    }

    // ****4 堆排序****

    // 例子：要求 将 27,15,19,18,28,34,65,49,25,37 这组数据 按照从小到大排序
    // 那么建立大根堆还是建立小根堆比较合适呢？
    // 要建立大根堆 ， 小根堆是不合适的
    // 要求是对数组本身来进行排序



    // 步骤 ： 先将其变成大根堆 ， 然后再将0下标的值跟最后一个待排序的值进行交换
    // 然后在将剩余的部分调整为大跟堆 ， 再进行交换，依次类推

    // 如果要求的是从大到小排序建立的是一个小根堆
    // 升序： 建大根堆
    // 降序： 建小根堆
    

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = { 27,15,19,18,28,34,65,49,25,37 };
        testHeap.initElem(array);
        testHeap.creatHeap(); // 这就是大根堆
        System.out.println("!!!!!!!!!!!!!!!");

        // 开始进行排序
        testHeap.heapSort();
        System.out.println();
    }

}